import java.util.ArrayList;
import java.util.List;

public class NQueens {
    private List<List<String>> results = new ArrayList<>();
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        boolean[] columns = new boolean[n]; // 列
        boolean[] diag1 = new boolean[2 * n]; // 主对角线
        boolean[] diag2 = new boolean[2 * n]; // 副对角线
        backtrack(0, new ArrayList<>(), columns, diag1, diag2);
        return results;
    }

    private void backtrack(int row, List<String> board, boolean[] columns, boolean[] diag1, boolean[] diag2) {
        if (row == n) {
            results.add(new ArrayList<>(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            int id1 = row - col + n; // 主对角线
            int id2 = row + col; // 副对角线

            if (columns[col] || diag1[id1] || diag2[id2]) {
                continue; // 列或对角线已被占用
            }

            // 放置皇后
            columns[col] = true;
            diag1[id1] = true;
            diag2[id2] = true;
            StringBuilder sb = new StringBuilder(".".repeat(n));
            sb.setCharAt(col, 'Q'); // 在当前行放置皇后
            board.add(sb.toString());

            // 递归下一行
            backtrack(row + 1, board, columns, diag1, diag2);

            // 撤销放置皇后
            board.remove(board.size() - 1);
            columns[col] = false;
            diag1[id1] = false;
            diag2[id2] = false;
        }
    }
}